1. Technical Field
Present invention embodiments relate to accessing set membership information, and more specifically, to cache-efficient access of set membership information using multilevel data structures to identify non-matching rows of database tables for join or other operations.
2. Discussion of the Related Art
Filters are data structures that may be used in testing whether an element is a member of a set. The results of the test indicate either that the element is not in the set or is possibly in the set. In other words, false positive matches are possible, but false negatives are not. Examples of filters include Bloom filters, counting filters, compact approximators, and related objects.
Filters may be used in a relational database management system (RDBMS) to improve the speed of a join operation by filtering out outer table rows that lack matching inner table rows without having to access a larger data structure such as a hash table. In this context, the filter is sometimes referred to as a “join filter.” Typically, a join filter takes the form of a bitmap of hash values for join keys of the inner table.
A larger filter will tend to produce fewer collisions and therefore fewer false positive results than a smaller filter. However, random look-ups into a very large data structure may result in cache misses, thereby reducing or negating the speed improvement provided by the filter.